package fordemo

class NQueen {
    def queens(n: Int): List[List[(Int, Int)]] = {
        def placeQueen(k: Int): List[List[(Int, Int)]] = {
            if (k == 0)
                List(List())
            else
                for {
                    queens <- placeQueen(k - 1)
                    column <- 1 to n
                    queen = (k, column)
                    if isSafe(queen, queens)
                } yield queen :: queens
        }

        placeQueen(n)
    }


    def isSafe(queen: (Int, Int), queens: List[(Int, Int)]): Boolean = {
        queens forall (q => !inCheck(queen, q))
    }

    def inCheck(tuple: (Int, Int), tuple1: (Int, Int)) =
        tuple._2 == tuple1._2 ||
                (tuple._1 - tuple1._1).abs == (tuple._2 - tuple1._2).abs

}
object Test3{
    def main(args: Array[String]): Unit = {
        val nq=new NQueen
        println(nq.queens(5))
    }
}
